package com.zyk.leetcode;

import java.util.*;

/**
 * @author zhangsan
 * @date 2021/5/1 10:11
 */
public class C690 {

    static class Employee {
        public int id;
        public int importance;
        public List<Integer> subordinates;
    };

    // 一个员工有多个直系下属, 和直系下属的下属们, 多叉树, 求指定员工和他的下属们的重要度之和
    public static int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> map = new HashMap<>();
        for (Employee employee : employees) {
            map.put(employee.id, employee);
        }
        return dfs(map.get(id), map);
    }

    private static int dfs(Employee employee, Map<Integer, Employee> map) {
        int importance = employee.importance;
        for (Integer id : employee.subordinates) {
            importance += dfs(map.get(id), map);
        }
        return importance;
    }

    // bfs
    public static int getImportance2(List<Employee> employees, int id) {
        Map<Integer, Employee> map = new HashMap<>();
        for (Employee employee : employees) {
            map.put(employee.id, employee);
        }

        Queue<Integer> q = new LinkedList<>();
        q.add(id);
        Employee cur;
        int ans = 0;
        while (!q.isEmpty()) {
            cur = map.get(q.poll());
            ans += cur.importance;
            q.addAll(cur.subordinates);
        }
        return ans;
    }


    // for test
    public static void main(String[] args) {

    }

}
